package wj.d826;

import java.math.BigInteger;
import java.util.ArrayList;
import java.util.List;

public class Solution {
    public String solution(int[] nums, int k) {
        List<BigInteger> total = new ArrayList<>();
        total.add(new BigInteger("0", 10));
        backTrack(nums, 0, k, new ArrayList<Integer>(), total);
        return total.get(0).mod(new BigInteger("1000000007", 10)).toString();
    }

    // n为当前访问到的位置,从0开始 到 nums.length结束,没到一次结束则为一个正确的结果
    // savedList存储已经选择好的值
    private void backTrack(int nums[], int n, int k, List<Integer> savedList, List<BigInteger> total) {
        if (n == nums.length) { //
            total.set(0, total.get(0).add(new BigInteger("1", 10)));
        } else if (nums[n] != 0) { //有数                 // 当前位置有数，不需要填，直接加入savedList，继续向后走
            savedList.add(nums[n]);
            backTrack(nums, n + 1, k, savedList, total);
            savedList.remove(savedList.size() - 1);
        } else { // 丢失
            int start = savedList.size() > 0 ? savedList.get(savedList.size() - 1) : 1;   // start 表示当前位置可以选择的起始值，此值为最小为上一结点的值或1（如果没有上一个结点的话）
            int end = k;                                                                  // end 表示当前位置可以选择的最大值， 为其右边界，看其右边出现的值或则为k
            int idx = n + 1;
            while (idx < nums.length && nums[idx] == 0) {
                idx++;
            }
            if (idx < nums.length && nums[idx] < k) {
                end = nums[idx];
            }
            if (end < start) {
                return;
            }
            for (int i = start; i <= end; i++) {
                savedList.add(i);
                backTrack(nums, n + 1, k, savedList, total);
                savedList.remove(savedList.size() - 1);
            }
        }
    }


    public int dpSolution(int[] nums, int k) {
        long[][] dp = new long[nums.length][k + 1];
        if (nums[0] == 0) {
            for (int i = 1; i <= k; i++) {
                dp[0][i] = 1;
            }
        } else {
            dp[0][nums[0]] = 1;
        }
        for (int i = 1; i < nums.length; i++) {
            int curNum = nums[i];
            if (curNum == 0) {
                for (int t = 1; t <= k; t++) {
                    for (int j = 0; j <= t; j++) {
                        dp[i][t] += dp[i - 1][j];
                    }
                }
            } else {
                for (int j = 0; j <= curNum; j++) {
                    dp[i][curNum] += dp[i - 1][j];
                }
            }
        }
        long total = 0;
        for (int i = 1; i <= k; i++) {
            total += dp[nums.length - 1][i];
        }
        return new BigInteger(total + "", 10).mod(new BigInteger("1000000007", 10)).intValue();
    }


    public static void main(String[] args) {
        int[] nums = new int[]{0, 0, 0, 0, 0, 67, 0, 0};
        int k = 100;
        int solution = new Solution().dpSolution(nums, k);
        System.out.println(solution);
    }
}
